package src.greedy_algorithms;

import java.util.Arrays;

/**
 * @author starsea
 * @date 2024-09-01 17:41
 */

public class Test08 {
    //合并区间问题

    /**
     * 1.先排序
     * 第一类是按照左端点排序第二类按照右端点去排序
     * 2.总结规律，进而得出这个问题的解决策略
     */
    public static void main(String[] args) {
        int[][] intervals = {{1,3},{8,10},{2,6},{15,18}};
        int [][] arr=merge(intervals);
    }
    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        int[][]arr=new int[intervals.length][2];
        arr[0]=intervals[0];
        int j=0;
        for(int i=1;i<intervals.length;i++)
        {
            int[] tmp=intervals[i];
            //可以合并
            if(arr[j][0]<=tmp[0] && arr[j][1]>=tmp[0])
            {
                arr[j][1]=Math.max(tmp[1],arr[j][1]);

            }
            //不可以合并
            else {
                j++;
                arr[j]=tmp;
            }

        }
        arr=Arrays.copyOf(arr,j+1);
        return arr;
    }

}
